The invention relates generally to data compression. More specifically, the invention relates to a method and apparatus for compressing image data utilizing an encoding technique which results in reduced distortion or error in the data.
Numerous fields of endeavor make use of vector quantization processing. One newly emerging application is data compression. The preferred embodiment of the invention will be described with particular reference to compression of image signals, though such an illustration is not a limitation on its scope.
A quantizer is a device which represents one signal which can take on a large number of values by another signal which can take on only a limited number of values. A four bit analog-to-digital converter, for example, represents the value of a continuously varying (i.e., analog) signal by a digital signal which can have only one of sixteen values. Scaler quantizers operate on signals having a single degree of freedom, such as an analog-to-digital converter operating on a voltage signal. Vector quantizers operate on signals having multiple degrees of freedom as will be discussed more fully below.
A vector quantizer for compressing video images conceptually divides the image into numerous small areas called pixels (a term formed from the words "picture" and "element"). Pixels are sufficiently small that the intensity of the image is approximately constant across the pixel area. For example, a black and white image of a house might be divided into a grid of 600 rows and 600 pixels per row. Each pixel would be like a small dot in the image. A group of pixels together would form a vector which can be thought of as a small subimage. For example a 6.times.6 square patch of pixels forms a vector which may be a portion of a shadow, or part of the roof line against a light background. Vectors formed from an image shall be called image vectors. The present invention operates on vectors which, for the illustrated example, are image vectors. In general, any source of vector signals may be used, and vectors which are subject to quantization are more generally referred to as input vectors.
While a black and white image serves as an example here, vectors might also be formed from red, green, or blue levels from a color image. They might also be formed from Y,I and Q components of a color image, or from transform coefficients of an image signal on which a Hadamard, Fourier, or other transform has operated.
Numerous methods exist for manipulating an image to form image vectors. For example, a television camera might generate an analog video signal in a raster scan format having 600 scan lines per frame. An analog-to-digital converter could then digitize the video signal at a sampling rate of 600 samples per scan line. Digital signal processing equipment can then store the digital samples, and group them into vectors. The process of digitizing an analog video signal is a form of scaler quantization which is similar to but distinct from methods of vector quantization. The discussion which follows assumes that one of many methods well known in the art of signal processing can be used to produce input digital image signals.
Before quantizing an image, a vector quantizer stores a set of "codebook" vectors in memory. Codebook vectors are vectors which are chosen to be representative of commonly found image vectors. The quantizer stores a sufficient variety of codebook vectors so that at least one closely matches each of the many vectors that might be found in the full image. Each codebook vector is assigned a unique identification code. The set of all codebook vectors is called a codebook.
In practice, the identification code for a codebook vector may be an address in a memory which stores the vector values. The precise order of the entries may be arbitrary, or it may be selected according to some property of the vectors.
When quantizing a full image, a vector quantizer divides the full image into a series of image vectors. For each image vector, the vector quantizer identifies one closely matching codebook vector. The vector quantizer then generates a new signal made up of the series of the identification codes of the selected codebook entries.
Regeneration of the full image can be accomplished by a device which has the complete codebook stored in memory. The device regenerates the image signal by replacing each ID code in the quantized signal with its corresponding codebook vector. The regenerated image differs from the original image, because codebook entries do not precisely match the original image vectors. The difference is called distortion or loss. Some forms of compression result in little or no loss. In effect, the input signal is changed in form but not in quality. While such compression techniques may not significantly affect or reduce bandwidth or processing time, other advantages such as improved signal quality or equipment compatibility may result. However, when system constraints exist, it may be necessary to suffer a certain level of distortion. The amount of such distortion which is tolerable depends, in part, on whether it is noticeable. In video transmission systems for example, the viewer may be the best judge of whether the distortion is in fact acceptable. Some vector quantizer systems have produced acceptable distortion with conventional video formats (i.e. 512.times.512 pixels). High definition television (HDTV) however has approximately 5 times the data of conventional TV formats. Accordingly compression techniques which produce tolerable distortion levels for conventional television may not work with HDTV. Also, if bandwidth requirements can be reduced without loss of picture quality, channel capacity may be increased.